package com.lw.leetcode.stack.b;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * b
 * stack
 * 907. 子数组的最小值之和
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/9 14:11
 */
public class SumSubarrayMins {


    public static void main(String[] args) {
        SumSubarrayMins test = new SumSubarrayMins();

        // 17
        int[] arr = {3, 1, 2, 4};

        // 444
//        int[] arr = {11,81,94,43,3};

        int i = test.sumSubarrayMins(arr);
        System.out.println(i);
    }

    public int sumSubarrayMins(int[] arr) {
        int length = arr.length;
        Stack<Integer> values = new Stack<>();
        Stack<Integer> indexs = new Stack<>();
        long sum = 0L;
        long[] s = new long[length + 1];
        for (int i = 0; i < length; i++) {
            int v = arr[i];
            while (!values.isEmpty() && values.peek() >= v) {
                values.pop();
                indexs.pop();
            }
            int t = indexs.isEmpty() ? -1 : indexs.peek();
            s[i + 1] = (s[t + 1] + (i - t) * (long) v) % 1000000007;
            sum = (s[i + 1] + sum) % 1000000007;
            values.add(v);
            indexs.add(i);
        }
        return (int) sum;
    }
}
